﻿module KDTreeModule

open System
open Microsoft.Xna.Framework
open System.Collections

type KDTree =
    |Branch of BoundingBox * Structures.X3dModel list * KDTree * KDTree
    |Leaf of BoundingBox * Structures.X3dModel list

let split_list (lst:'a list) n = 
    let mutable count = n
    let mutable firstList = []
    let mutable secondList = []
    let stackList = new Stack()
    stackList.Push lst
    while (stackList.Count) <> 0 do
        
        match (stackList.Pop()) with
        | :? ('a list) as x-> ()
        | _ -> ()
        ()
    let before = Seq.take n (Seq.ofArray lst)
    let after = Seq.skip n (Seq.ofArray lst)
    (before,after)

//let test3 x = match x with 
//                  |0 -> 0
//                  |x when x>0 -> 1
//                  |x when x<0 -> 1
//                  |_ -> 0
//
//let test2 = fun x->
//                match x with 
//                |0 -> 0
//                |x when x>0 -> 1
//                |x when x<0 -> 1
//                |_ -> 0
//
//let test  = function
//               |0 -> 0
//               |y when y>0 -> 1
//               |y when y<0 -> 1
//               |_ -> 0

let split (models:Structures.X3dModel List) =
    let modelsArray = Array.ofList models
    let vec3Model (model:Structures.X3dModel) =
        model.Vertices 
            |> Array.map (fun x -> (Vector3.Transform(x.Position,model.World)), model)
    let V3Array = 
        Array.concat (Array.map vec3Model modelsArray)
    let variances (pts:(Vector3 * Structures.X3dModel) array) = 
         let mean (el:(float32 [])) = 
            (Array.sum el) / (float32)el.Length
         let variance (el:(float32 []))= 
            let media = mean el
            (Array.sum (Array.map (fun n -> pown (n-media) 2) el) / (float32)el.Length)
         let (points,y) = Array.unzip pts
         (variance (points 
                        |> Array.map (fun x -> x.X)),
          variance (points 
                        |> Array.map (fun x -> x.Y)),
          variance (points 
                        |> Array.map (fun x -> x.Z)))         
    let (vx,vy,vz) = variances V3Array
    let (pt_before,pt_after) =
        if ((vx>=vy)&&(vx>=vz)) then 
            split_list (Array.sortBy (fun (x:Vector3,y) -> x.X) V3Array) (V3Array.Length/2)
            else if (vy>=vx)&&(vy>=vz) then 
                    split_list (Array.sortBy (fun (x:Vector3,y) -> x.Y) V3Array) (V3Array.Length/2)
                 else
                    split_list (Array.sortBy (fun (x:Vector3,y) -> x.Z) V3Array) (V3Array.Length/2)
    let (before,after) = 
        (Set.ofSeq (Seq.distinct (Seq.map (fun (x,y) -> y) pt_before)),
         Set.ofSeq (Seq.distinct (Seq.map (fun (x,y) -> y) pt_after)))
    let between = Set.intersect before after
    (Set.toList between,
     Set.toList before,
     Set.toList after)    
let rec build (models:Structures.X3dModel list) =
    let pts = models 
                |> List.map (fun x -> Seq.ofArray x.Vertices)
                |> Seq.concat
                |> Seq.map (fun x -> x.Position)  
    let pts = List.ofSeq pts  
    let (between,left,right) = 
                            if (pts.Length < 1000) then (models,[],[])
                            else split models
    match (between,left,right) with
    |([],[],[]) -> Leaf (new BoundingBox(),[])
    |(b,[],[]) -> 
                    let leafPtf = models 
                                    |> List.map (fun x -> Seq.ofArray x.Vertices)
                                    |> Seq.concat
                                    |> Seq.map (fun x -> x.Position)  
                    Leaf (BoundingBox.CreateFromPoints(leafPtf),b)                     
    |(b,l,r) ->                     
                let branchPts =b
                                |> List.map (fun x -> Seq.ofArray x.Vertices)
                                |> Seq.concat
                                |> Seq.map (fun x -> x.Position)  
                Branch (BoundingBox.CreateFromPoints(branchPts),b,build (l),build (r))

//let rec intersectBB root (camera:BoundingFrustum) = match root with
//                                                    |Leaf(bb,[]) -> []
//                                                    |Leaf(bb,lst) -> if (camera.Intersects(bb)) then lst
//                                                                        else []
//                                                    |Branch(bb,lst,left,right) -> if (camera.Intersects(bb)) then lst@(intersectBB left camera)@(intersectBB right camera)
//                                                                                    else (intersectBB left camera)@(intersectBB right camera)